package algorithm.niuke;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class 二叉搜索树的最小绝对差 {
    /*
     * 给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。 输入:
     * 
     * 1 \ 3 / 2
     * 
     * 输出: 1
     * 
     * 解释: 最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
     */
    List<Integer> list = new ArrayList<>();

    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        Collections.sort(list);
        int min = 1 << 30;
        for (int i = 1; i <= list.size(); i++) {
            min = Math.min(min, Math.abs(list.get(i - 1) - list.get(i)));
        }
        return min;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}
